package 极客算法训练营.chapter09;

import java.util.*;

public class 单词接龙 {

    class Solution2 {
        private int minDistance = Integer.MAX_VALUE;

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            char[] begin = beginWord.toCharArray();
            char[] end = endWord.toCharArray();
            char[][] wordListArray = new char[wordList.size()][];
            for (int i = 0; i < wordList.size(); i++) {
                wordListArray[i] = wordList.get(i).toCharArray();
            }
            dfs(begin, end, wordListArray, 0);
            return minDistance == Integer.MAX_VALUE ? 0 : minDistance + 1;
        }

        public void dfs(char[] begin, char[] end, char[][] wordListArray, int distance) {
            if (Arrays.equals(begin, end)) {
                minDistance = Math.min(minDistance, distance);
                return;
            }

            for (int i = 0; i < wordListArray.length; i++) {
                //先判断是否访问过
                if (wordListArray[i] == null) continue;
                //再判断长度是否一致
                char[] word = wordListArray[i];
                if (begin.length != word.length) continue;
                int diff = 0;
                for (int j = 0; j < word.length; j++) {
                    if (begin[j] != word[j]) {
                        diff++;
                    }
                }
                if (diff == 1) {
                    wordListArray[i] = null;
                    dfs(word, end, wordListArray, distance + 1);
                    wordListArray[i] = word;
                }
            }
        }
    }

    class Solution {
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            //使用哈希表存储字典
            Set<String> wordSet = new HashSet<>(wordList);
            if (wordSet.isEmpty() || !wordSet.contains(endWord)) {
                return 0;
            }
            //存储已访问过的字符串
            Set<String> visited = new HashSet<>();
            //层级双端队列
            Deque<String> queue = new LinkedList<>();
            //设定初始状态
            queue.addLast(beginWord);
//            wordSet.remove(beginWord);
            visited.add(beginWord);
            int step = 1;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    String string = queue.pollFirst();
                    //寻找与当前字符串相差为1的元素
                    for (String s : wordSet) {
                        if (!visited.contains(s) && compDiff(string, s) == 1) {
                            if (s.equals(endWord)) return step + 1;
                            queue.addLast(s);
                            visited.add(s);
                        }
                    }
                }
                step++;
            }
            return 0;
        }
        public int compDiff(String s1, String s2) {
            int diff = 0;
            char[] s1s = s1.toCharArray();
            char[] s2s = s2.toCharArray();
            for (int i = 0; i < s1s.length; i++) {
                if (s1s[i] != s2s[i]) {
                    diff++;
                }
            }
            return diff;
        }
    }
}
